//
// Created by mac on 2023/11/25.
//

// 最小覆盖字串
class Solution
{
public:
    string minWindow(string s, string t)
    {
        // 1、初始化（题目说：s 和 t 由英文字母组成，所以我们可以使用定长数组来代替哈希表）
        int hash1[128] = {0}, hash2[128] = {0}, kind = 0;
        for(const auto e : t)
            if(hash2[e]++ == 0) ++kind;
        // 2、滑动窗口
        int begin = -1, len = INT_MAX;
        for(int left = 0, right = 0, count = 0; right < s.size(); ++right)
        {
            // 进窗口 && 更新count
            char in = s[right];
            if(++hash1[in] == hash2[in]) ++count;
            // 更新count && 出窗口
            while(count == kind)
            {
                // 更新结果
                if(right - left + 1 < len)
                {
                    begin = left;
                    len = right - left + 1;
                }
                char out = s[left++];
                if(hash1[out]-- == hash2[out]) --count;
            }
        }
        // 3、返回值
        return len == INT_MAX ? "" : s.substr(begin, len);
    }
};
